package algorithm.difficult;

import pojo.TreeNode;

/**
 * 给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
 * <p>
 * 两个节点之间的路径长度 由它们之间的边数表示。
 * <p>
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-univalue-path
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LongestUnivaluePath {

    int max = 0;

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) return 0;
        def(root);
        return max;
    }


    //int 代表递归的当前节点，节点值val能够连接的最大次数
    public int def(TreeNode node) {
        int left = 0;
        int right = 0;
        if (node.left != null) {
            int temp  = def(node.left);
            if (node.left.val == node.val) {
                left = temp + 1;
            }
        }
        if (node.right != null) {
            int temp = def(node.right);
            if (node.right.val == node.val) {
                right = temp + 1;
            }
        }
        //v字型，将左右值相加获得最大值。
        if (node.left != null && node.right != null && node.left.val == node.val && node.right.val == node.val) {
            max = Math.max(max, left + right);
        }
        max = Math.max(max, Math.max(left, right));
        return Math.max(left, right);
    }
}
